[ABC236B] Who is missing
题目分析
- 总共有 $4N$ 张卡片，每个数字 $1$ 到 $N$ 各有 $4$ 张；
- 给出洗牌后移除一张卡片后的 $4N-1$ 张卡片数字序列；
- 需要找出被移除的那张卡片上的数字。
解题思路
- 每个数字原本有 $4$ 张，移除一张后该数字的出现次数将变为 $3$；
- 只需统计给出的卡片中每个数字出现的次数，找到出现次数少于 $4$ 的数字即为答案；
- 具体而言：
- 统计所有数字出现的次数；
- 找出出现次数为 $3$ 的数字。
实现步骤
- 初始化长度为 $N$ 的计数数组
cnt[100005]，设为全局变量初始化都为 $0$；
- 输入数据后逐个更新计数；执行
cnt[x]++ 即可。
- 遍历计数数组找出计数为 $3$ 的索引（数字）；
for (int i = 1; i <= N; i++) if (cnt[i] == 3)
- 输出该数字即可。
- 注意输入一共输入 $4N-1$ 个数字，而求答案只需要循环到 $N$。
复杂度分析
- 时间复杂度：$O(N)$，主要是遍历输入和计数数组；
- 空间复杂度：$O(N)$，用于计数数组。
总结
- 利用数字出现次数的特点简化问题；
- 统计计数是最直接且高效的方法；
- 适合大规模数据，符合题目要求。